1. Field of the Invention
The present invention relates generally to a digital memory.
2. Description of the Related Art
In modern electronic devices, switches are used to connect a number of senders to a number of receivers, such that any of the senders can deliver a data stream (or packet) to any of the receivers. To accommodate variability in communication between the senders and receivers, the switches may use packet buffer memories to store packets received from the senders, which cannot immediately be transmitted to the intended receivers.
One conventional packet buffer memory configuration uses an input buffer connected to each of a number of input ports, wherein a different input buffer is connected to a different one of the number of input ports. Each of the different input buffers associated with the number of input ports is connected to a switching substrate (e.g., crossbar switch or shared bus) which is connected to a number of output ports. In this configuration, if there are two packets stored in the same input buffer, but destined for different output ports, only one packet can make progress even if both output ports are available. This situation exists because the two packets share a common connectivity into the switching substrate. Also in this configuration, the input buffer associated with the input port that is receiving the packet must have sufficient space available to receive the entire packet. The packet cannot be stored in another input buffer associated with another input port.
Another conventional packet buffer memory configuration uses an output buffer connected to each of a number of output ports, wherein a different output buffer is connected to a different one of the number of output ports. Each of the different output buffers associated with the number of output ports are connected to a switching substrate (e.g., crossbar switch or shared bus) which is also connected to a number of input ports. In this configuration, if two packets arrive from two different input ports at the same time and are destined for a common output port, only one packet can make progress. This situation exists because the two packets must share a connectivity into the common output port. Also in this configuration, a packet may be stored in any available output buffer, but the entire packet must be stored in the same output buffer. Therefore, the output buffer must have sufficient space to store the packet before the packet can progress.
In either of the conventional packet buffer memory configurations mentioned above, a complicated buffer allocation mechanism is required to achieve efficient utilization of the input ports, output ports, and buffer memories. In order to avoid contention for resources when a new packet arrives, the system must take into account a number of factors, among others, such as (a) availability of space in each buffer, (b) whether a packet is currently being deposited into or retrieved from each buffer, and (c) the number of packets that are currently waiting for deposition in each buffer.
In view of the foregoing, there is a need for a more efficient shared buffering solution that can be implemented without requiring either a complicated buffer allocation scheme or high speed memory circuitry.